package com.xiyou.week03.tree;

import javafx.util.Pair;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 429. N 叉树的层序遍历
 * 给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
 * <p>
 * 树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
 *
 * @ClassName：levelOrder
 * @Author：西柚
 * @Date：2022/1/14 6:35 下午
 * @Versiion：1.0
 */
public class LevelOrder {

    /**
     * 输入：root = [1,null,3,2,4,null,5,6]
     * 输出：[[1],[3,2,4],[5,6]]
     *
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(Node root) {
        Queue<Pair<Node, Integer>> q = new LinkedList<>();
        List<List<Integer>> seq = new ArrayList<>();
        if (root == null) {
            return seq;
        }
        q.add(new Pair<>(root, 0));
        while (!q.isEmpty()) {
            Node node = q.peek().getKey();
            Integer depth = q.poll().getValue();
            if (depth >= seq.size()) {
                seq.add(new ArrayList<>());
            }
            seq.get(depth).add(node.val);
            for (Node child : node.children) {
                q.add(new Pair<>(child, depth + 1));
            }
        }
        return seq;
    }

    class Node {
        public int val;
        public List<Node> children;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    }
}
